C/C++ Users Group Library 1996 July/C-C++ Users Group Library July 1996.iso/vol_200/245_01/lca.doc

Text File | 1987-10-26 | 32KB | 546 lines

[LCA.DOC]
[Harold V. McIntosh, 20 May 1987]

1. History.

Cellular Automata have been studied as a part of the abstract theory of
computation since the time that John von Neumann became interested in the
possibility of constructing self-reproducing automatic factories. Since
actual factories and physical machinery involve a myriad of practical but
non-essential details, he eventually followed a suggestion of Stanislaw Ulam
that an abstract mathematical model would be more amenable to a demonstration
of the possibilities of universal construction and self reproduction. He
worked out a scheme for such an automaton, in terms of a cellular space
occupying a two dimensional grid, in which each cell would be found in
one of twenty eight states.

The details of von Neumann's construction remained unpublished at the time
of his death, but were subsequently edited and published by A. W. Burks.
Ulam's work on functional iteration and his experiments on nonlinear mappings
was reported in conference proceedings, and cellular automata became a topic
in the theory of abstract machines, along with the work of Edward. F. Moore,
Claude Shannon, and others. Of course there were even earlier beginnings, in
the studies of Warren S. McCulloch and Walter Pitts in 1943 on neural nets,
followed in 1951 by a certain mathematical abstraction by S. C. Kleene, and
even in the general ideas on Cybernetics introduced by Norbert Wiener in his
famous book.

Public awareness of cellular automata can mostly be attributed to John Horton
Conway's interest in finding a simpler configuration than von Neumann's
and exploring its capabilities. Some of his results were presented in 1970 as
an ecological game called Life, at a time when such concerns were popular, in
Martin Gardner's monthly Mathematical Games column in Scientific American.
For a period of about three years Robert T. Wainwright maintained a quarterly
newsletter disseminating discoveries made by Martin Gardner's readers, some
of which were followed up in later columns in Scientific American. Many of the more
interesting results were obtained with the help of the graphics facilities
of a PDP-6 computer in MIT's Artificial Intelligence Laboratory.

When microcomputers began to attract popular attention, Conway's game of Life
became one of the early inspirations for an application; Cromemco's "Dazzler,"
a color video controller and one of the earliest peripherals, was frequently
used to display the evolution of Life configurations. An early issue of Byte
magazine summarized many results which had appeared in Wainwright's newsletter
a decade earlier, but had still not reached mass circulation. Some other
magazines, such as Omni, revived the topic, and in recent years Scientific
American has returned to the subject, most recently in A. K. Dewdney's
Computer Recreations, the current successor to Martin Gardner's column.

Professional scientific interest has received a considerable impetus from
the investigations of Stephen Wolfram, who undertook a computer based
search through the properties of one dimensional automata, guided by some
concepts from the realm of nonlinear dynamics and statistical mechanics.
In any event, the microcomputers, programming languages, and video displays
which are currently available are sufficient for many experimental studies
of cellular automata, many of whose results have considerable artistic merit.

A recent article exploring the aesthetic side of automata theory was one
entitled Abstract Mathematical Art, by Kenneth E. Perry, which appeared in
the December, 1986, issue of Byte. The article included a Basic program for
use on IBM/PC compatible computers, with indications that a Pascal version
was available from the magazine, and a statement that the author himself
had used machine language to quickly seek out the examples enumerated in his
article. Several of them were shown in striking color photographs.

The idea of a one dimensional cellular automaton is quite simple, an its
evolution in time is ideal for a two dimensional presentation, as on a video
screen. To start with, a cell is a region, even a point, with differing forms,
called states. For convenience, these states are usually numbered with small
integers beginning with zero, rather than described. For the purposes of
automata theory the nature of the states does not matter, only their relation
to one another, and the way they change with time according to their
envoironment. Since they are abstract, they can just as well be represented
by colored dots on a video screen, which is what leads to interpreting them
as part of an abstract artistic design.

To make a one dimensional automaton, a series of cells is strung out in a
line, the simplest assumption being that all the cells have the same number
of similar states, and that the rules of evolution will be the same for all
of them. The idea of forming the cells into a line implies a linear order,
but of course other arrangements are possible, both in terms of the dimension
and the connectivity of the cells. This is the second element of definition
for a cellular automaton - the relationship between the cells, or the kinds
of neighborhoods which they form. Again, the simplest neighborhood would
consist of a cell and its nearest two neighbors, and generally speaking we
would take a neighbborhood to consist of r neighbors on each side, giving
2r+1 for the total number of cells in a neighborhood.

There are some small quibbles to be made. If a chain is finite, it has ends,
which surely do not have the same neighborhoods as the interior cells. Either
they can be treated differently, or the chain can be imagined to close into
a ring, which would preserve the uniformity of all the neighborhoods. Also,
it is considered preferable to work with symmetric neighborhoods, each one
centered on its own cell, rather than worrying about irregular neighborhoods.
An exception occurs because there are times when only one neighbor would be
desired, always on the same side.

Thus there arises the notation (k,r) for a linear cellular automaton which
has k states within each cell, and such that it, together with r cells on
either side, is considered to form a neighborhood.

There is one final ingredient in the definition of a cellular automaton,
which is the rule of transition by which the cell changes state from one
generation to the next, conventionally assumed to be the same rule for each
neighborhood. It is the judicious selection of a rule as much as anything
that makes a particular automaton interesting or not.

Conway's game of Life was the result of a particular choice of rule for a
two dimensional binary automaton - two states per cell - whose neighborhoods
contained the cell in the center and the eight cells touching it, four of
them laterally and four of them diagonally. The announced critera by which
that particular rule was chosen were that a field of cells should neither
dwindle away to nothing - all zeroes - or eventually fill up completely -
all ones. Reportedly, he examined many different rules before choosing the
 particular one which gave us his famous game; even so, so much variety was
encountered with that one particular rule that years passed before many
others were studied.

Wolfram's recent work, mostly done at the Institute for Advanced Studies in
Princeton, systematically examined all the possible rules for one dimensional
automata. His recent book summarizes his and some other results in an extensive
appendix. In two dimensions there are far too many possibilities - more so
even than in one dimension - for there to be a chance to try everything, even
with a very fast computer. Notwithstanding, Dewdney's column in a recent issue
of Scientific American describes a three dimensional variant of Life examined
by Carter Bays. However, the one dimensional automata of type (2,1) represent
a reasonable starting point for systematic studies.

For such an automaton, a neighborhood contains three cells, while each can
have two states, so altogether there